#include <cstdio>

int f[ 500001 ], p[ 500001 ];

int main( )
{
    int i, j, n, len, low, mid, high, a, b, t = 1;
    while ( scanf("%d", &n) != EOF )
    {
        if ( n == 0 )
        {
            printf("Case %d:\nMy king, at most 0 road can be built.\n\n", t++);
            continue;
        }
        for ( i = 0; i < n; i++ )
        {
            scanf("%d%d", &a, &b);
            p[ a ] = b;
        }
        f[ 0 ] = 0;
        f[ 1 ] = p[ 1 ];
        len = 1;
        for ( i = 2; i <= n; i++ )
        {
            low = 0;
            high = len;
            while ( low <= high )
            {
                mid = ( high + low ) >> 1;
                if ( f[ mid ] < p[ i ] )
                    low = mid + 1;
                else
                    high = mid - 1;
            }
            f[ low ] = p[ i ];
            if ( len < low )
                len++;
        }
        printf("Case %d:\n", t++);
        if ( len == 1 )
            printf("My king, at most 1 road can be built.\n\n");
        else
            printf("My king, at most %d roads can be built.\n\n", len);
    }
    return 0;
}
